#pragma once
#include<iostream>
#include<vector>
#include<queue>
#include<assert.h>
using namespace std;

template<class K,class V>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	BSTreeNode* _parent;
	pair<K, V>_kv;
	BSTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};


template<class K, class V>
class BSTree
{
public:
	BSTree<K,V> () = default;
	using node = BSTreeNode<K,V>;
	
	BSTree(const pair<K, V>& kv)
		:_root(new node(kv))
		, _size(0)
	{}

		
	bool insert(const pair<K, V>& kv)
	{
		node* newnode = new node(kv);
		if (_root == nullptr)
		{
			_root = newnode;
			return true;
		}
		node* parent = nullptr;
		node* cur = _root;
		while (cur)
		{
			K key = newnode->_kv.first;
			K rkey = cur->_kv.first;
			parent = cur;
			if (key > rkey)
				cur = cur->_right;
			else if (key < rkey)
				cur = cur->_left;
			else
				return false;
		}

		newnode->_parent = parent;
		if (newnode->_kv.first < parent->_kv.first)
			parent->_left = newnode;
		else
			parent-> _right = newnode;

		return true;
	}
	void inorder()
	{
		_inorder(_root);
		cout <<"\n----inorder finish----\n";
	}

private:
	void _inorder(node* root)
	{
		if (!root)
			return;
		cout << root->_kv.first<< ' ';
	}

	node* _root;
	size_t _size;
};